// 常规DFS + 剪枝100%
impl Solution {
    pub fn makesquare(mut matchsticks: Vec<i32>) -> bool {
        let (mut m, n) = (matchsticks.len() as i32, matchsticks.iter().sum::<i32>());
        if n % 4 != 0 { return false; }

        fn dfs(m: i32, n: i32, side: &mut Vec<i32>, matchsticks: &Vec<i32>) -> bool {
            if m == -1 { return true; }
            for i in 0..4 {
                if side[i] == n || side[i] + matchsticks[m as usize] > n || (i > 0 && side[i] == side[i - 1]) { continue; }
                side[i] += matchsticks[m as usize];
                if dfs(m - 1, n, side, matchsticks) { return true; }
                side[i] -= matchsticks[m as usize];
            }
            false
        }
        matchsticks.sort();
        dfs(m - 1, n / 4, &mut vec![0; 4], &matchsticks)
    }
}

// 回溯
impl Solution2 {
    pub fn makesquare(mut matchsticks: Vec<i32>) -> bool {
        let sum = matchsticks.iter().sum::<i32>();
        let l = sum >> 2;
        if sum % 4 != 0 || matchsticks.iter().any(|x| x > &l) {
            return false;
        }
        matchsticks.sort_by(|a, b| b.cmp(a));

        let len = matchsticks.len();
        // 用来存储当前火柴放在哪条边上，也是当前火柴所放位置的起始范围。从0开始放。
        let mut map = vec![0; len];
        // 当前放的火柴索引
        let mut i = 0;
        // 四条边的状态，放入一根火柴或者回溯的时候就更新长度，
        let mut arr = [0, 0, 0, 0];
        let mut res = true;

        loop {
            // 标识当前火柴放到边上没有
            let mut flag = false;
            // 因为是依次放的，map[i] >= 4的时候就是没有合适的位置可以放了。准备回溯
            if map[i] < 4 {
                for j in map[i]..4 {
                    // 当前边可以放下火柴，更新map，更新边
                    if arr[j] + matchsticks[i] <= l {
                        map[i] = j;
                        arr[j] += matchsticks[i];
                        flag = true;
                        break;
                    }
                }
            }

            // 如果最后一根火柴放到边上了，那就表示完成了正方形
            if flag && i == len - 1 {
                break;
            }
            // 回溯的边界，第0根火柴任何地方都放不下了，return false
            if !flag && i == 0 {
                res = false;
                break;
            }
            // 回溯，当前火柴的起始置为0，上一根火柴放的边长度更新，上一根火柴的起始位置 += 1;
            if !flag {
                map[i] = 0;
                i -= 1;
                let j = map[i];
                arr[j] -= matchsticks[i];
                map[i] += 1;
            } else {
                // 正常放下了，就开始放下一根火柴
                i += 1;
            }
        }
        res
    }
}


// 也不知道怎么调用的？？